// 1. 二分法
// step 1# 二分查找函数：返回是否找到 target
bool binarySearch(int* row, int size, int target) {
    int left = 0, right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;  // 防止溢出
        if (row[mid] == target) return true;  // 找到
        else if (row[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return false;  // 未找到
}

// step 2# 主函数：判断 target 是否在二维矩阵中出现
bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) {
    for (int i = 0; i < matrixSize; i++) {
        if (binarySearch(matrix[i], matrixColSize[i], target)) {
            return true;
        }
    }
    return false;
}

// 2. 右上角排除法
bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) {
    int m = matrixSize, n = matrixColSize[0];
    int i = 0, j = n - 1; // 从右上角开始
    while (i < m && j >= 0) { // 还有剩余元素
        if (matrix[i][j] == target) {
            return true; // 找到 target
        }
        if (matrix[i][j] < target) {
            i++; // 这一行剩余元素全部小于 target，排除
        } else {
            j--; // 这一列剩余元素全部大于 target，排除
        }
    }
    return false;
}
